package com.lark.algorithm.train.onChapter.linkedList;

/**
 * @author btmood
 * @version 1.0
 * @apiNote
 *
 * 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,1,2]
 * 输出：[1,2]
 * 示例 2：
 *
 *
 * 输入：head = [1,1,2,3,3]
 * 输出：[1,2,3]
 *
 *
 * 提示：
 *
 * 链表中节点数目在范围 [0, 300] 内
 * -100 <= Node.val <= 100
 * 题目数据保证链表已经按升序 排列
 *
 * @since 2024-05-21 14:46
 */
public class D20240521Q83_删除排序链表中的重复元素 {

    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummyHead = new ListNode(Integer.MIN_VALUE, head);
        ListNode prevNode = dummyHead;
        while (prevNode.next != null) {
            if (prevNode.val == prevNode.next.val) {
                ListNode nextNode = prevNode.next.next;
                prevNode.next.next = null;
                prevNode.next = nextNode;
            } else {
                prevNode = prevNode.next;
            }
        }
        return dummyHead.next;
    }

    // 删除递增链表里的重复元素
    // 返回新链表的头节点
    public ListNode deleteDuplicates2(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode newHead = deleteDuplicates2(head.next);
        if (newHead == null) {
            return head;
        } else {
            if (head.val == newHead.val) {
                return newHead;
            } else {
                head.next = newHead;
                return head;
            }
        }
    }


    public static class  ListNode {
        int val;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
        ListNode next;

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            ListNode cur = next;
            sb.append(val);
            while (cur != null) {
                sb.append("=>");
                sb.append(cur.val);
                cur = cur.next;
            }
            return sb.toString();
        }
    }

}
